For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
0answers
16 views

Finite sequence with no two consecutive terms

$\newcommand{\N}{\mathbb{N}}$ Let $n \in \N$, we define $[n] \doteq \{1 , \ldots, n \}$. Consider the following $$ H_n^k \doteq \{ z \in [n]^k  \mid \forall i \in [k-1]: \ z_{i+1} \neq z_i + 1 \} $$ ...
0
votes
1answer
28 views

Counting and Probability String Length

Consider strings that can be made up from the set $\{a, b, c, d, e, f, \cdots, z, 0, 1, 2, \cdots, 9\}$ 1) How many strings of length 8 contain either the letter '$x$' or '$1$'? 2) What is the ...
0
votes
1answer
11 views

Unimodality of sequence

I have to show the following: a) was pretty easy to show, however, I am not able to get something useful out of the recursive definition in b) and I have no idea how to approach c). What bijection ...
2
votes
1answer
43 views

How many non prime factors are in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$.

to find non prime factors in the number $N=2^5 \cdot 3^7 \cdot 9^2 \cdot 11^4 \cdot 13^3$. First I tried finding all the factors by adding 1 to each of the exponents and then multiplying them and ...
6
votes
3answers
207 views

How many permutations

How many permutations $\pi \in S_{2n} $ for which $\exists a\in [2n] $ such that set $\lbrace a,\pi (a),\pi ^2(a),\pi^3(a),... \rbrace $ has exactly $n$ elements. I need help to solve this.
0
votes
1answer
47 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
0
votes
0answers
17 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
2
votes
1answer
20 views

Family of sets without 2 disjunct elements, prove the statement

Suppose, that the $F \subseteq 2^{[n]}$ family of sets doesn't have two disjunct elements. Prove, that there is always an $F' \subseteq 2^{[n]}$ family of sets, which contains $F$, $F'$ has no ...
2
votes
2answers
31 views

How do you find the the sum of a list of permutations?

If you are given the digits 1, 2, 3 and 4 and then are asked to find the number of different 4-digit numbers you can make (repetition is allowed). We can multiply $4 \times 4 \times 4 \times 4 = 256$ ...
0
votes
1answer
19 views

Congruence for Stirling Number of first kind $s(n,k)$ when $n$ is prime

Let $s(n,k)$ be the Stirling numbers of first kind: $$\prod_{k=0}^{k=n-1}(x-k) =\sum_{k=0}^{k=n}s(n,k)x^k$$ $p$ is prime $\iff$ for all $k\in\{2,..,p-1\}$, $s(p,k)\equiv0\ mod\ p $ How ...
-4
votes
1answer
28 views

A question on basic combinatorics. [on hold]

I wonder in how many ways $n$ women and $n$ men can be sat down a circular table such that no man sits beside a man and no woman sits beside a woman?
1
vote
1answer
20 views

Counting sequences using Catalan Numbers

Count the number of sequences $a_{1},...,a_{2015}$ such that: $a_{i}\in \{-1,1\}$, and $\sum _{i=1} ^ {2015} a_{i}=7$, and $\sum _{i=1} ^{j} a_i >0$ for every $1\leq j\leq 2015$ I assume we have ...
1
vote
0answers
38 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
2
votes
1answer
18 views

Combinatorics question- $5$ points on a sphere [on hold]

Diffuser $5$ points on a sphere. Prove there is a close half-sphere that has at least $4$ points on.
1
vote
1answer
38 views

The greatest number of points of intersection of n circles and m straight lines is-

The question is about combinatorics. I have no idea on how to start solving the problem. Please guide me. $(a) 2mn+ {m \choose 2}$ $(b) \frac{1}{2}m(m-1)+n(2m+n-1)$ $(c) {m \choose 2}+2({n \choose ...
1
vote
0answers
23 views

Intersecting Family of subsets of size k

Suppose that $k$ divides $n$. Then an intersecting family $F$ of $k$-subsets of an $n$-set $X$ has size at most $n-1\choose k-1$. My book doesn't give a very intuitive proof of this fact and I am ...
2
votes
3answers
53 views

The number of choices of 3 kinds of crust and up to 6 distinct toppings

David has a pizza shop. There are 3 kinds of crust and 6 different toppings he can chose from. If customers can have as many toppings as they'd like but may not order double of one topping, how ...
0
votes
1answer
21 views

For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the ...
1
vote
1answer
32 views

2x2 grid game problem

A friend of mine is attempting to make a webpage that has a game for a 2x2 grid that is similar to the old North, South, East, West game. I cannot for the life of me figure this out. Essentially, ...
2
votes
4answers
151 views

The coefficients of $\frac{1}{\cos(x)}$ are odd

Let's consider $G(z)=\dfrac{1}{\cos(z)}$ as an exponential generating function of the Euler numbers' sequence. How to prove that all $a_{i}$ in the expansion of$\dfrac{1}{\cos(z)}=\sum_{k=0}^{ ...
0
votes
1answer
19 views

Rewrite the sum of the products by interpretation

By interpreting what the following sum is counting and then counting the same object in a different way, rewrite the following sum as a product of two terms (without any sum): $\sum\limits_{k=m}^n$ ...
0
votes
0answers
17 views

How to find the number of words of length $h$ in a subsets $A$?

Let $L=\{0,1\}^*$ (the set of binary words on $0$ and $1$), Given a tuple of words $(w_1,w_2,\cdots,w_n)\in L^n$ and a function $\sigma:[1,n]\to [1,n]$ define the following set: ...
0
votes
2answers
23 views

Permutations; group of 5 boys, 10 girls. What's the probability the person the 4th position is a boy?

Problem description: A group of 5 boys and 10 girls is lined up in random order -- that is, each of the 15! permutations is assumed to be equally likely. What is the probability that the person in ...
0
votes
1answer
25 views

Some men and women are randomly assigned seats at a round table and no two persons of the same sex are seated next to each other. Probability of this?

Four women and four men are assigned seats at random at a round table. what is the probability that no two persons of the same sex will be sitting next to each other?
5
votes
0answers
32 views

Riddle: Assigning Students into Groups

Suppose you had a classroom with 25 students. You want to assign 6 homework assignments over the course of the term and for each of these assignments students will work in groups of 5. But you want to ...
1
vote
0answers
25 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
0
votes
1answer
41 views

no. of disordered pairs of disjoint subsets

I found this question in a book. The same question has been asked before, but I want a more generalised and rigorous, so to speak, answer. The question reads- " Consider the set $S= \{1,2,3,4\}.$ ...
1
vote
2answers
41 views

Consider all the permutations of the word “ENDEANOEL”

Consider all the permutations of the word "ENDEANOEL" : 1)What is the number of permutations containing the word "ENDEA" ? I can't understand how to approach this problem!! 2)Number of permutations ...
0
votes
1answer
18 views

Reverse permutation, number of inversions, descents, major index

If $w=a_1a_2...a_n \in S_n $, then let $w^r=a_n....a_2a_1$, the reverse of $w$. Express inv($w^r$), des($w^r$) and maj($w^r$) in terms inv($w$), des($w$), maj($w$), respectively. It from Stanley's ...
2
votes
1answer
26 views

How do people find the number of ways you can put together a rubiks cube?

Just curious. How do people actually find the number of ways you can put together a rubiks cube? How do you find the number of choices? Do you use the same permutation formula? Insight would be ...
3
votes
3answers
102 views

Is this permutations or combinations?

I am a bit confused. When we use the multiplicative principle are we finding the number of permutations or combinations. An example of using this principle is where I have $5$ shirts $3$ pairs of ...
0
votes
1answer
35 views

Combination formula?

I know there is a formula for finding the different combinations when you are dividing them in groups: $$\binom{n}{r} = \frac{n!}{(n-r)!\, r!}$$ However, what if you just want to find the number of ...
0
votes
0answers
20 views

Other than the icosahedron in which each vertex has degree 5, is there any triangulation of the sphere that meets the following three conditions?

Every vertex has degree > 3. There is no separating triangle (a triangle with vertices of the graph both inside and outside the triangle). Every vertex-coloring using exactly four colors consists of ...
-3
votes
0answers
45 views

some amazing properties of combinatorial numbers [on hold]

I want to prove $$ C_{2^{i+1}-k-1}^k=\frac{(2^{i+1}-k-1)(2^{i+1}-k-2)\cdots(2^{i+1}-k-(k-1))(2^{i+1}-2k)}{k(k-1)\cdots 2\cdot 1} $$ is even, for all $k=1,2,3,\cdots, 2^i-1$. Here $i\geq 1$. How to ...
-1
votes
2answers
22 views

How many ways are there to arrange three of the letters chosen from the set ABCDE? [on hold]

Please show your work. I've been looking at this problem for over an hour now and havn't been able to solve it. Thank you!
0
votes
1answer
38 views

Number of paths in a graph with infinite nodes

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node? We are only concerned with paths that ...
0
votes
2answers
19 views

Prove that if $k\mid n$ then $p(A_k)={1\over k}$

Let $n$ be a natural number, $n=p_1^{a_1}\cdot...\cdotp_m^{a_m}$. Let us randomly choose a number between 1 and $n$ with a uniform, equal chance. Let us denote the event "The number chosen is ...
-5
votes
1answer
34 views

Need help in solving [on hold]

A group of $60$ children attend an after school club. Of these, $35$ children play football and $29$ play hockey. Three children do not play either football or hockey. Find the number of children ...
0
votes
1answer
33 views

Generating function of derangements

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have. In the lecture we have proven the following generating function for ...
1
vote
1answer
44 views

What is the probability that you get $i$ on the $i^{th}$ trial?

What is the probability that you get $i$ on the $i^{th}$ trial? Match = Get result $i$ on $i^{th}$ trial. What is the probability of $M = 0,1,2,...,6$ matches when: Note: I'm not asking you to do ...
5
votes
3answers
98 views

Find the coefficient of $x^{30}$.

Find the coefficient of $x^{30}$ in the given polynomial $$ \left(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}\right)^5 $$ I don't know how to solve problems with such high degree.
1
vote
2answers
41 views

Combinatorics Recurrence relation

Let $h_n$ be a number sequence where $h_n = 3h_{n-1} - 2h_{n-2}$ with $h_0 = 0$ and $h_1 = 1$. Compute the ordinary generating function of $h_n$ and then using the generating function compute a ...
2
votes
2answers
18 views

Probability of Two Suits within Three cards, within 4 cards

I am trying to calculate what is the probability of the 3 random cards of 52-pack containing at least two of the same suit. I am also trying to do the same for the four card variant (so, the ...
0
votes
4answers
54 views

Combinatorial Proof of an Instance of the Binomial Theorem

Give a combinatorial proof of the following instance of the binomial theorem. For any positive integer $k$, $(k + 1)^{n}$ = $\sum\limits_{i=0}^{n}$ ${n}\choose{i}$$k^{i}$. I have looked at this for ...
-1
votes
0answers
27 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
1
vote
0answers
30 views

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to ...
0
votes
0answers
18 views

Combinatorics Question for generating fuctions [on hold]

Any tips/helps would be greatly appreciated! Let h_n be a number sequence where h_n = 3h_(n-1) - 2h_(n-2) with h_0 = 0 and h_1 = 1. Compute the ordinary generating function of h_n, and then compute a ...
0
votes
1answer
19 views

All subsets of nonnegative integers such that $a+2b = n$ has one solution for every positive integer n

My friend tackled this problem awhile ago and gave it to me recently. To reiterate, I am trying to find all subsets $S$ of the nonnegative integers such that the equation $a+2b = n$, where $a$ and $b$ ...
-4
votes
1answer
30 views

Combinatorics Generating Functions [on hold]

Any tips/comments would be greatly appreciated! Compute the generating function of the number sequence $h_n = (-2)^n n^2$ where $n\geq 0$.
0
votes
0answers
8 views

Finding a permutation class that has a growth rate greater than 1 and less than 0?

In a permutation class, there is an upper growth rate such that $gr(C)=\limsup_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$ and a lower growth rate such that $\liminf_{n\rightarrow \infty}=\sqrt[n]{|C_n|}$. ...