# Tagged Questions

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.

244 views

### Combinatorics Problem - Clients using two seperate services

A financial group offers personal insurance and stock trading brokerage services. In total 10,000 people use their services. The group has 7,000 clients who use the insurance service and 5,000 who use ...
30 views

### Delannoy Paths and Pell Sequence Relation

I have the Pell sequence $a_n = 2a_{n-1} + a_{n-2}$ for $n \geq 2$ and $a_0 = 1, a_1=2$. I am trying to employ counting logic from Delannoy paths to show that $a_n = \sum\frac{(i+j+k)!}{i!j!k!}$ for ...
149 views

### Logic & Reasoning Question

At a track meet, every group of $n$ participants shares exactly one common friend. Suppose runner $P$ has the largest number of friends. Determine how many friends $P$ has. Assume for this question: ...
124 views

The question is as stated in the title up to symmetries of $D_{16}$. I know this has to do with the following two formulas: If $G=D_{16}$ is the group acting on the set $S$ of different necklaces, ...
72 views

### Discrete mathematics, sets, increasing functions

I have this assignment where I'm really lost and not sure how to solve. The assignment follows: We have two sets, $A = \{1,2,3,4,5,6,7\}$ and $X=\{a,b,c,d,e,f\}$. We say that a function $F$ is ...
45 views

### How many different games are there in bridge?

I know that there are ${52 \choose 13}$ hands. I was thinking maybe it was ${52 \choose 1} {52 \choose 39} {52 \choose 26} {52 \choose 13}$.
38 views

### finding exponential generating function by recursion in order to find the formal power series

If i define the number of permutation on n objects with order that divides 2 i get the recursion: a(n+2)=a(n+1)+(n+1)*a(n). then i can get the exponential generating function i(x)=sum(a(n)/n!*x^n)=...
58 views

### binomials product alternating sum calculation

I need to somehow prove that $\sum\limits_{k = 0}^{n - 1} {n \choose k} {3 n - k - 1 \choose 2 n - k}(-1)^k = (-1)^{n + 1} {2 n - 1 \choose n}$. I didn't manage to do it using induction or any ...
32 views

### How to find the ordinary generating function of a sequence from its exponential generating function?

Let $a$ and $b$ be positive constants. Suppose that $e^{at^2 + bt} = \sum_{k = 0}^\infty c_k t^k / k!$ is the exponential generating function of a sequence $\{c_k = c_k(a, b)\}$. How does one compute ...
118 views

### Cyclic shift in size K of a permutatoin P.

I am stucked in this question,can anyone please help me out.P is a permutation of integers 1, 2,... N. We want to change it a little. To do this, we choose an integer K that satisfies an inequality 2 ≤...
47 views

### Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
57 views

### The probability that people select identical balls: two-person case is simple, but more-than-2-person case is complicated.

There are $n$ distinct balls. There are $p$ people, and the $i$th person selects $q_i$ distinct balls from these $n$ distinct balls. The question is: what is the probability that $q_0$ balls are ...
40 views

### Sum with binomial coefficients

How to find the sum $\sum_{k=1}^{m} k\binom{n}{k} \binom{n}{m-k}$? I also would be glad to know the generating function $\sum_{k=0}^{m} \binom{n}{k} \binom{n}{m-k}x^k$. Thank you.
55 views

### Number of permutations of $n$ objects with order 3 or 4

I am trying to see how I can find the number of permutations pi - lets say $a(n)$ - of $n$ objects with pi^3=id or pi^4=id. for example - $a(4)=24$, $a(5)=76$, $a(6)=336$. Is it something that can be ...
66 views

### Find number of integer solutions of linear equation

We're given an equation. $$x_1 + x_2 + x_3 + x_4 + x_5 =21$$ $$x_i \ge 0$$ aditionnal conditions are: $$0\le x_1 \le 3$$ $$1 \le x_2 \le4$$ $$15 \le x_3$$ Task is to find all integer solutions to ...
27 views

### Mapping the Number of Functions

I have read here how to figure out the number of functions between two sets A and B. But how do I figure the number of ways a function can be expressed within a another function. For example: (Let's ...
60 views

### Unique unclosed paths on torus grid

Consider a grid of points in the shape of torus with in my case $n=16$ points around the toroidal direction and $m=7$ points around the poloidal direction. Now draw a line by starting at any grid ...
65 views

### The number of ways to fill a 3 by 3 grid

I am currently studying the problem of combination. And when I am doing an exercise, I saw the following question: There is a 3 x 3 grid, and for each cells in the grid, two players take turn to fill ...
57 views

### Different Possible Combinations from Different Sets

I have 4 different sets A={a,b} B={c,d} C={e,f,g,h} D={h,i} I want to find the sum of distinct 2,3,4 letter combinations. Two letters cannot be chosen from the same set. (i.e) For a 3 letter ...
44 views

### Gaussian binomial coeffcient

Let the Gaussian Binomial Coefficient be defined for a prime $q$ as $$\binom{N}{l}_{q}:=\prod_{i=0}^{l-1} \frac{q^{N-i}-1}{q^{l-i}-1}$$ Now I want to show that, for $D>2$...
50 views

### Combinatorics theory question

Anyone know how to do this? In real life, if a person A is a friend of a person B then B is a friend of A. Let now S be the set of students in our department. Prove that there are at least two ...
44 views

### A combinatoric/probability puzzle

A horse race has four horses A, B, C and D. The probabilities for each horse to finish first or second are P(A)=80%, P(B)=60%, P(C)=40% and P(D)=20%. The probabilities add up to 200% because one ...
33 views

### Will removing the return leg from a traveling salesman problem ever change the results?

In a typical traveling salesman problem one starts at an origin point, visits a number of points once, then returns to the origin point in the most efficient way possible. Are there any scenarios in ...
95 views

114 views

### Combinatorial problem about splitting a finite set of real numbers

Given a finite set $X$ of real numbers greater than one. I'm looking for disjoint sets $A,B$ such that $X=A\cup B$ and such that $$\prod_{x\in A}x\leq\prod_{x\in B}x\,.$$ Especially am I interested ...
Is there a way to show that $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$ where $a,b$ are positif integer with out using induction ?